package tree;

public class AVLTreeNode<T1,T2>{
    private T1 id;
    private T2 element;
    private AVLTreeNode<T1,T2> left;
    private AVLTreeNode<T1,T2> right;

    private boolean leftPre;
    private boolean rightPost;
    public AVLTreeNode() {
    }

    public boolean isLeftPre() {
        return leftPre;
    }

    public void setLeftPre(boolean leftPre) {
        this.leftPre = leftPre;
    }

    public boolean isRightPost() {
        return rightPost;
    }

    public void setRightPost(boolean rightPost) {
        this.rightPost = rightPost;
    }

    public AVLTreeNode(T1 id, T2 element) {
        this.id = id;
        this.element = element;
        this.left = null;
        this.right = null;
    }

    public T1 getId() {
        return id;
    }

    public void setId(T1 id) {
        this.id = id;
    }

    public T2 getElement() {
        return element;
    }

    public void setElement(T2 element) {
        this.element = element;
    }

    public AVLTreeNode<T1,T2> getLeft() {
        return left;
    }

    public void setLeft(AVLTreeNode<T1,T2> left) {
        this.left = left;
    }

    public AVLTreeNode<T1,T2> getRight() {
        return right;
    }

    public void setRight(AVLTreeNode<T1,T2> right) {
        this.right = right;
    }

    public void preOrderPrint(){
        printNode();
        if(left!=null){
            left.preOrderPrint();
        }
        if(right!=null){
            right.preOrderPrint();
        }
    }
    public void printNode(){
        System.out.println("id:"+id+",element:"+element);
    }

    public int leftTreeHeight(){
        if(this.left==null){
            return 0;
        }
        return this.left.treeHeight();
    }

    public int rightTreeHeight(){
        if(this.right==null){
            return 0;
        }
        return this.right.treeHeight();
    }

    public int treeHeight(){
        return Math.max(left==null?0:left.treeHeight(),right==null?0:right.treeHeight())+1;
    }
    public void leftRotate(){
        AVLTreeNode<T1,T2> node = new AVLTreeNode<>();
        node.setElement(this.getElement());
        node.setId(this.getId());
        this.setElement(this.right.getElement());
        this.setId(this.right.getId());
        node.left = this.left;
        node.right = this.right.left;
        this.left = node;
        this.right = this.right.right;
    }
    public void rightRotate(){
        AVLTreeNode<T1,T2> node = new AVLTreeNode<>();
        node.setElement(element);
        node.setId(id);
        element=left.getElement();
        id=left.getId();
        node.right=right;
        node.left=left.right;
        left=left.left;
        right=node;
    }
    public void balanceAdjustment(){
        if(leftTreeHeight()-rightTreeHeight()>1){
            if(left.rightTreeHeight()>left.leftTreeHeight()){
                leftRotate();
            }
            rightRotate();
            return;
        }
        if(rightTreeHeight()-leftTreeHeight()>1){
            if(right.leftTreeHeight()>right.rightTreeHeight()){
                rightRotate();
            }
            leftRotate();
            return;
        }
    }
    public void add(AVLTreeNode<T1,T2> node) {
        Comparable<T1> comparable = (Comparable<T1>) node.getId();
        int result = comparable.compareTo(id);
        if(result!=0){
            if(result<0){
                if(left==null){
                    left = node;
                }else {
                    left.add(node);
                }
            }else {
                if(right==null){
                    right = node;
                }else {
                    right.add(node);
                }
            }
            balanceAdjustment();
        } else {
            this.setElement(node.getElement());
        }
    }

    public T2 search(T1 id) {
        T2 result = null;
        if(this.id.equals(id)){
            result = element;
        }

        if(result==null&&left!=null){
            result = left.search(id);
        }

        if(result==null&&right!=null){
            result = right.search(id);
        }

        return result;
    }

    public void postOrderPrint() {
        if(right!=null){
            right.postOrderPrint();
        }
        if(left!=null){
            left.postOrderPrint();
        }
        printNode();
    }

    public void postOrderThreads(){
        if(right!=null){
            right.postOrderThreads();
        }
        if(left!=null){
            left.postOrderThreads();
        }

    }
    public void delLeafNode(AVLTreeNode<T1,T2> parent){
        Comparable comparable = (Comparable) this.id;
        if(comparable.compareTo(parent.getId())<0){
            parent.left=null;
        }
        else {
            parent.right=null;
        }
    }
    public void delOneChildNode(AVLTreeNode<T1,T2> parent){
        Comparable comparable = (Comparable) this.id;
        if(comparable.compareTo(parent.getId())<0){
            parent.left=this.left!=null?this.left:this.right;
        }
        else {
            parent.right=this.left!=null?this.left:this.right;
        }
    }
    public void delHaveChildNode(){
        AVLTreeNode<T1,T2> delNode;
        if(this.left!=null){
            delNode = searchLeftTreeMaxNode();
        }else {
            delNode = searchRightTreeLeastNode();
        }
        T1 saveId = delNode.getId();
        T2 saveElement = delNode.getElement();
        delete(delNode.getId(),this);
        this.setId(saveId);
        this.setElement(saveElement);
    }
    public void delTwoChildNode(){
        AVLTreeNode<T1,T2> delNode = searchRightTreeLeastNode();
        delete(delNode.getId(),this);
        this.setId(delNode.getId());
        this.setElement(delNode.getElement());
    }

    private AVLTreeNode<T1,T2> searchRightTreeLeastNode() {
        AVLTreeNode<T1,T2> node = this.right;
        while(node.getLeft()!=null){
            node = node.getLeft();
        }
        return node;
    }
    private AVLTreeNode<T1,T2> searchLeftTreeMaxNode() {
        AVLTreeNode<T1,T2> node = this.left;
        while(node.getRight()!=null){
            node = node.getRight();
        }
        return node;
    }

    public void delete(T1 id, AVLTreeNode<T1,T2> parent) {
        Comparable comparable = (Comparable) this.id;
        int result = comparable.compareTo(id);
        if(result<0&&this.right!=null){
            this.right.delete(id,this);
        }else if(result>0&&this.left!=null){
            this.left.delete(id,this);
        }else if(result==0) {

            if(this.left==null&&this.right==null){
                if(parent==null){
                    this.id=null;
                }else {
                    /*叶子节点*/
                    delLeafNode(parent);
                }
            }else if(this.left==null&&this.right!=null||
                this.right==null&&this.left!=null){
                delHaveChildNode();
            }else if(this.left!=null&&this.right!=null){
                delHaveChildNode();
            }
        }
    }
}
